package com.example.algorithm.dynamicprogramming;

/**
 * 给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内
 * （可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
 * <p>
 * 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 10⁹ + 7 取余 后的结果。
 * <p>
 * 示例 1：
 * 输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
 * 输出：6
 * <p>
 * 示例 2：
 * 输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
 * 输出：12
 */
public class Leetcode576_FindPaths {
    static class Solution {
        /**
         * 动态规划
         * 动态规划的状态由移动次数、行和列决定，定义 dp[i][j][k] 表示球移动 i 次之后位于坐标 (j, k)的路径数量
         * 如果球移动了 i 次之后位于坐标 (j,k) ， 则移动第 i+1 次之后，球一定位于和坐标 (j,k) 相邻的一个坐标记为 (i', j')
         * 当 0 <= j' < m 且 0 <= k' < n时，球在移动 i+1 次之后没有出界， 将dp[i][j][k] 的值加到 dp[i+1][j'][k']；
         * 否则，球在第 i+1 次移动之后出界，将 dp[i][j][k] 的值加到出界的路径数
         *
         * @param m
         * @param n
         * @param maxMove
         * @param startRow
         * @param startColumn
         * @return
         */
        public int findPaths2(int m, int n, int maxMove, int startRow, int startColumn) {
            final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            final int MOD = (int) Math.pow(10, 9) + 7;
            int[][][] dp = new int[maxMove + 1][m][n];
            dp[0][startRow][startColumn] = 1; // 一次都不移动就在原位置(状态初始化)
            int res = 0;
            for (int i = 0; i < maxMove; i++)
                for (int j = 0; j < m; j++)
                    for (int k = 0; k < n; k++) {
                        if (dp[i][j][k] > 0) {  // 通过移动 i 次可以到达位置(j, k)
                            for (int[] direction : directions) { // 尝试向相邻的位置进行移动
                                int tmpX = j + direction[0], tmpY = k + direction[1];
                                if (tmpX >= 0 && tmpX < m && tmpY >= 0 && tmpY < n) // 下一次移动未移动到界外，就需要更新通过移动i + 1 次可以到达(tmpX, tmpY)的路径数
                                    dp[i + 1][tmpX][tmpY] = (dp[i + 1][tmpX][tmpY] + dp[i][j][k]) % MOD;
                                else // 下一次移动就到了界外，则需要更新结果
                                    res = (res + dp[i][j][k]) % MOD;
                            }
                        }
                    }
            return res;
        }

        /**
         * 解法一：回溯(超时)
         *
         * @param m
         * @param n
         * @param maxMove
         * @param startRow
         * @param startColumn
         * @return
         */
        public int findPaths1(int m, int n, int maxMove, int startRow, int startColumn) {
            final int MOD = (int) Math.pow(10, 9) + 7;
            class Stub {
                int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
                int res = 0;

                public void dfs(int curPosX, int curPosY, int remainMoveCount) {
                    // 移动出了边界且剩余移动次数大于等于 0 ， 说明本次移动路径可以移出边界
                    if ((curPosX == -1 || curPosX == m || curPosY == -1 || curPosY == n) && remainMoveCount >= 0) {
                        res = (res + 1) % MOD;
                        return;
                    }
                    if (remainMoveCount == 0) return; // 不可以移动了，返回

                    for (int[] direction : directions) // 尝试朝四个方向进行移动
                        dfs(curPosX + direction[0], curPosY + direction[1], remainMoveCount - 1);
                }
            }

            Stub stub = new Stub();
            stub.dfs(startRow, startColumn, maxMove);
            return stub.res % MOD;
        }

        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            return findPaths2(m, n, maxMove, startRow, startColumn);
        }
    }

    public static void main(String[] args) {
        int m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0;
        m = 8; n = 7; maxMove = 16; startRow = 1; startColumn = 5;
        System.out.println(new Solution().findPaths(m, n, maxMove, startRow, startColumn));
    }
}
